{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recommender Systems 2020/21\n",
    "\n",
    "### Practice 4b - FunkSVD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Movielens10M: Verifying data consistency...\n",
      "Movielens10M: Verifying data consistency... Passed!\n",
      "DataReader: current dataset is: <class 'Data_manager.Dataset.Dataset'>\n",
      "\tNumber of items: 10681\n",
      "\tNumber of users: 69878\n",
      "\tNumber of interactions in URM_all: 10000054\n",
      "\tValue range in URM_all: 0.50-5.00\n",
      "\tInteraction density: 1.34E-02\n",
      "\tInteractions per user:\n",
      "\t\t Min: 2.00E+01\n",
      "\t\t Avg: 1.43E+02\n",
      "\t\t Max: 7.36E+03\n",
      "\tInteractions per item:\n",
      "\t\t Min: 0.00E+00\n",
      "\t\t Avg: 9.36E+02\n",
      "\t\t Max: 3.49E+04\n",
      "\tGini Index: 0.57\n",
      "\n",
      "\tICM name: ICM_genres, Value range: 1.00 / 1.00, Num features: 20, feature occurrences: 21564, density 1.01E-01\n",
      "\tICM name: ICM_tags, Value range: 1.00 / 69.00, Num features: 10217, feature occurrences: 108563, density 9.95E-04\n",
      "\tICM name: ICM_all, Value range: 1.00 / 69.00, Num features: 10237, feature occurrences: 130127, density 1.19E-03\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from Notebooks_utils.data_splitter import train_test_holdout\n",
    "from Data_manager.Movielens.Movielens10MReader import Movielens10MReader\n",
    "\n",
    "data_reader = Movielens10MReader()\n",
    "data_loaded = data_reader.load_data()\n",
    "\n",
    "URM_all = data_loaded.get_URM_all()\n",
    "\n",
    "URM_train, URM_test = train_test_holdout(URM_all, train_perc = 0.8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<69878x10681 sparse matrix of type '<class 'numpy.float64'>'\n",
       "\twith 8000088 stored elements in Compressed Sparse Row format>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URM_train"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What do we need for FunkSVD?\n",
    "\n",
    "* User factor and Item factor matrices\n",
    "* Computing prediction\n",
    "* Update rule\n",
    "* Training loop and some patience\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_users, n_items = URM_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1: We create the dense latent factor matrices\n",
    "### In a MF model you have two matrices, one with a row per user and the other with a column per item. The other dimension, columns for the first one and rows for the second one is called latent factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_factors = 10\n",
    "\n",
    "user_factors = np.random.random((n_users, num_factors))\n",
    "item_factors = np.random.random((n_items, num_factors))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.10922357, 0.1400291 , 0.83540861, ..., 0.00427209, 0.61478403,\n",
       "        0.72202759],\n",
       "       [0.79784576, 0.1905475 , 0.76621221, ..., 0.72553039, 0.18384262,\n",
       "        0.19075107],\n",
       "       [0.0112557 , 0.38364501, 0.14426158, ..., 0.61721718, 0.48454021,\n",
       "        0.04158188],\n",
       "       ...,\n",
       "       [0.73182207, 0.18786462, 0.22171543, ..., 0.06294801, 0.18048496,\n",
       "        0.10350385],\n",
       "       [0.21114588, 0.40653902, 0.90383763, ..., 0.40786238, 0.50300933,\n",
       "        0.38190921],\n",
       "       [0.81091948, 0.18710044, 0.64201128, ..., 0.95273574, 0.76063279,\n",
       "        0.3603066 ]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_factors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0.497202  , 0.23804075, 0.76369035, ..., 0.70437787, 0.23605717,\n",
       "        0.61427761],\n",
       "       [0.00393812, 0.67987897, 0.68433483, ..., 0.69707505, 0.2039948 ,\n",
       "        0.22130279],\n",
       "       [0.54465904, 0.9514584 , 0.75404424, ..., 0.04597385, 0.99216349,\n",
       "        0.1186468 ],\n",
       "       ...,\n",
       "       [0.09989421, 0.07621387, 0.55361184, ..., 0.4095528 , 0.31555305,\n",
       "        0.70204314],\n",
       "       [0.44115908, 0.29720619, 0.08158752, ..., 0.96194354, 0.77475201,\n",
       "        0.03910538],\n",
       "       [0.85648627, 0.15503346, 0.67365132, ..., 0.20409353, 0.02832431,\n",
       "        0.30959996]])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_factors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2: We sample an interaction and compute the prediction of the current FunkSVD model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1929120"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "URM_train_coo = URM_train.tocoo()\n",
    "\n",
    "sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "sample_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(17025, 468, 3.0)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_id = URM_train_coo.row[sample_index]\n",
    "item_id = URM_train_coo.col[sample_index]\n",
    "rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "(user_id, item_id, rating)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.969457703505743"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "predicted_rating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The first predicted rating is a random prediction, essentially\n",
    "\n",
    "### Step 3: We compute the prediction error and update the latent factor matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.030542296494257"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prediction_error = rating - predicted_rating\n",
    "prediction_error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The error is positive, so we need to increase the prediction our model computes. Meaning, we have to increase the values latent factor matrices\n",
    "\n",
    "### Which latent factors we modify? All the factors of the item and user we used"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copy original value to avoid messing up the updates\n",
    "H_i = item_factors[item_id,:]\n",
    "W_u = user_factors[user_id,:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.07456019, 0.62647858, 0.13277896, 0.84962947, 0.00383289,\n",
       "       0.63947138, 0.74936389, 0.64903736, 0.57800548, 0.45869254])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.95626918, 0.53530823, 0.07668639, 0.36144233, 0.0690484 ,\n",
       "       0.8392761 , 0.38958578, 0.27577824, 0.25139705, 0.20128098])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "W_u"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Apply the update rule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "learning_rate = 1e-4\n",
    "regularization = 1e-5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.07682787, 0.64560732, 0.13683357, 0.87557549, 0.00394927,\n",
       "       0.65899391, 0.77224729, 0.6688577 , 0.59565659, 0.47270005])"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "user_factors_update = prediction_error * H_i - regularization * W_u\n",
    "user_factors_update"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.98547509, 0.5516515 , 0.07902724, 0.37247312, 0.07115726,\n",
       "       0.86490313, 0.40147713, 0.28419465, 0.25906952, 0.20742397])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_factors_update = prediction_error * W_u - regularization * H_i\n",
    "item_factors_update"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "user_factors[user_id,:] += learning_rate * user_factors_update \n",
    "item_factors[item_id,:] += learning_rate * item_factors_update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's check what the new prediction for the same user-item interaction would be"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.9700195703562"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "predicted_rating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The value is slightly higher than before, we are moving in the right direction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### And now? Sample another interaction and repeat... a lot of times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### WARNING: Initialization must be done with random non-zero values ... otherwise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prediction is 0.00\n",
      "Prediction error is 3.00\n"
     ]
    }
   ],
   "source": [
    "user_factors = np.zeros((n_users, num_factors))\n",
    "item_factors = np.zeros((n_items, num_factors))\n",
    "\n",
    "predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "\n",
    "print(\"Prediction is {:.2f}\".format(predicted_rating))\n",
    "\n",
    "prediction_error = rating - predicted_rating\n",
    "\n",
    "print(\"Prediction error is {:.2f}\".format(prediction_error))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "H_i = item_factors[item_id,:]\n",
    "W_u = user_factors[user_id,:]\n",
    "\n",
    "user_factors[user_id,:] += learning_rate * (prediction_error * H_i - regularization * W_u)\n",
    "item_factors[item_id,:] += learning_rate * (prediction_error * W_u - regularization * H_i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prediction after the update is 0.00\n",
      "Prediction error is 3.00\n"
     ]
    }
   ],
   "source": [
    "predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "\n",
    "print(\"Prediction after the update is {:.2f}\".format(predicted_rating))\n",
    "print(\"Prediction error is {:.2f}\".format(rating - predicted_rating))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Since the matrices are multiplied, if we initialize one of them as zero, the updates will always be zero and the model will not be able to learn."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's put all together in a training loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 100000 in 1.56 seconds, loss is 2.64. Samples per second 64263.03\n",
      "Iteration 200000 in 3.16 seconds, loss is 2.61. Samples per second 63247.17\n",
      "Iteration 300000 in 4.75 seconds, loss is 2.57. Samples per second 63140.78\n",
      "Iteration 400000 in 6.32 seconds, loss is 2.55. Samples per second 63337.47\n",
      "Iteration 500000 in 7.89 seconds, loss is 2.53. Samples per second 63359.57\n",
      "Iteration 600000 in 9.46 seconds, loss is 2.50. Samples per second 63394.41\n",
      "Iteration 700000 in 11.03 seconds, loss is 2.48. Samples per second 63436.56\n",
      "Iteration 800000 in 12.60 seconds, loss is 2.46. Samples per second 63473.24\n",
      "Iteration 900000 in 14.16 seconds, loss is 2.44. Samples per second 63542.15\n",
      "Iteration 1000000 in 15.74 seconds, loss is 2.42. Samples per second 63540.81\n"
     ]
    }
   ],
   "source": [
    "URM_train_coo = URM_train.tocoo()\n",
    "\n",
    "num_factors = 10\n",
    "learning_rate = 1e-4\n",
    "\n",
    "user_factors = np.random.random((n_users, num_factors))\n",
    "item_factors = np.random.random((n_items, num_factors))\n",
    "\n",
    "loss = 0.0\n",
    "start_time = time.time()\n",
    "\n",
    "for sample_num in range(1000000):\n",
    "    \n",
    "    # Randomly pick sample\n",
    "    sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "    user_id = URM_train_coo.row[sample_index]\n",
    "    item_id = URM_train_coo.col[sample_index]\n",
    "    rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "    # Compute prediction\n",
    "    predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "        \n",
    "    # Compute prediction error, or gradient\n",
    "    prediction_error = rating - predicted_rating\n",
    "    loss += prediction_error**2\n",
    "    \n",
    "    # Copy original value to avoid messing up the updates\n",
    "    H_i = item_factors[item_id,:]\n",
    "    W_u = user_factors[user_id,:]  \n",
    "    \n",
    "    user_factors_update = prediction_error * H_i - regularization * W_u\n",
    "    item_factors_update = prediction_error * W_u - regularization * H_i\n",
    "    \n",
    "    user_factors[user_id,:] += learning_rate * user_factors_update \n",
    "    item_factors[item_id,:] += learning_rate * item_factors_update    \n",
    "    \n",
    "    # Print some stats\n",
    "    if (sample_num +1)% 100000 == 0:\n",
    "        elapsed_time = time.time() - start_time\n",
    "        samples_per_second = sample_num/elapsed_time\n",
    "        print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/sample_num, samples_per_second))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What do we see? The loss oscillates over time, sometimes it goes down sometimes up.\n",
    "### How long do we train such a model?\n",
    "\n",
    "* An epoch: a complete loop over all the train data\n",
    "* Usually you train for multiple epochs. Depending on the algorithm and data 10s or 100s of epochs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 1259.03 seconds, or 20.98 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This model is relatively quick, less than 30 minutes\n",
    "\n",
    "### Let's see what we can do with Cython\n",
    "### First step, just compile it. We do not have the data at compile time, so we put the loop in a function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load_ext Cython"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "def do_some_training(URM_train):\n",
    "\n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    n_users, n_items = URM_train_coo.shape\n",
    "\n",
    "    num_factors = 10\n",
    "    learning_rate = 1e-4\n",
    "    regularization = 1e-5\n",
    "\n",
    "    user_factors = np.random.random((n_users, num_factors))\n",
    "    item_factors = np.random.random((n_items, num_factors))\n",
    "\n",
    "    loss = 0.0\n",
    "    start_time = time.time()\n",
    "\n",
    "    for sample_num in range(1000000):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        sample_index = np.random.randint(URM_train_coo.nnz)\n",
    "\n",
    "        user_id = URM_train_coo.row[sample_index]\n",
    "        item_id = URM_train_coo.col[sample_index]\n",
    "        rating = URM_train_coo.data[sample_index]\n",
    "\n",
    "        # Compute prediction\n",
    "        predicted_rating = np.dot(user_factors[user_id,:], item_factors[item_id,:])\n",
    "\n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Copy original value to avoid messing up the updates\n",
    "        H_i = item_factors[item_id,:]\n",
    "        W_u = user_factors[user_id,:]  \n",
    "\n",
    "        user_factors_update = prediction_error * H_i - regularization * W_u\n",
    "        item_factors_update = prediction_error * W_u - regularization * H_i\n",
    "\n",
    "        user_factors[user_id,:] += learning_rate * user_factors_update \n",
    "        item_factors[item_id,:] += learning_rate * item_factors_update    \n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 100000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = sample_num/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/sample_num, samples_per_second))\n",
    "\n",
    "    return loss, samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 100000 in 1.38 seconds, loss is 2.61. Samples per second 72406.42\n",
      "Iteration 200000 in 2.79 seconds, loss is 2.58. Samples per second 71757.29\n",
      "Iteration 300000 in 4.19 seconds, loss is 2.56. Samples per second 71611.80\n",
      "Iteration 400000 in 5.59 seconds, loss is 2.52. Samples per second 71513.70\n",
      "Iteration 500000 in 7.04 seconds, loss is 2.50. Samples per second 70978.19\n",
      "Iteration 600000 in 8.45 seconds, loss is 2.47. Samples per second 71035.36\n",
      "Iteration 700000 in 9.86 seconds, loss is 2.45. Samples per second 70989.75\n",
      "Iteration 800000 in 11.25 seconds, loss is 2.43. Samples per second 71138.57\n",
      "Iteration 900000 in 12.64 seconds, loss is 2.41. Samples per second 71209.65\n",
      "Iteration 1000000 in 14.06 seconds, loss is 2.39. Samples per second 71124.67\n"
     ]
    }
   ],
   "source": [
    "loss, samples_per_second = do_some_training(URM_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 1124.79 seconds, or 18.75 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The compiler is just porting in C all operations that the python interpreter would have to perform, dynamic tiping included. Have a look at the html reports in the Cython_examples folder\n",
    "\n",
    "### Now try to add some types: If you use a variable only as a C object, use primitive tipes\n",
    "\n",
    "* cdef int namevar\n",
    "* cdef double namevar\n",
    "* cdef float namevar\n",
    "* cdef double[:] singledimensionarray\n",
    "* cdef double[:,:] bidimensionalmatrix\n",
    "\n",
    "### Some operations are still done with sparse matrices, those cannot be correctly optimized because the compiler does not know how what is the type of the data.\n",
    "\n",
    "### To address this, we create typed arrays in which we put the URM_train data\n",
    "####  For example, this operation: user_id = URM_train_coo.row[sample_index]\n",
    "#### Becomes:\n",
    "#### cdef int user_id\n",
    "#### cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "#### user_id = URM_train_coo_row[sample_index]\n",
    "\n",
    "### We can also skip the creation of the items_in_user_profile array and replace the np.random call with the faster native C function rand()\n",
    "\n",
    "\n",
    "### We now use types for all main variables\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "from libc.stdlib cimport rand, srand, RAND_MAX\n",
    "\n",
    "def do_some_training(URM_train):\n",
    "\n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    n_users, n_items = URM_train_coo.shape\n",
    "    cdef int n_interactions = URM_train.nnz\n",
    "    \n",
    "    cdef int sample_num, sample_index, user_id, item_id, factor_index\n",
    "    cdef double rating, predicted_rating, prediction_error\n",
    "\n",
    "    cdef int num_factors = 10\n",
    "    cdef double learning_rate = 1e-4\n",
    "    cdef double regularization = 1e-5\n",
    "    \n",
    "    cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "    cdef int[:] URM_train_coo_col = URM_train_coo.col\n",
    "    cdef double[:] URM_train_coo_data = URM_train_coo.data\n",
    "    \n",
    "    cdef double[:,:] user_factors = np.random.random((n_users, num_factors))\n",
    "    cdef double[:,:] item_factors = np.random.random((n_items, num_factors))\n",
    "    cdef double H_i, W_u\n",
    "    cdef double item_factors_update, user_factors_update\n",
    "                \n",
    "    cdef double loss = 0.0\n",
    "    cdef long start_time = time.time()\n",
    "\n",
    "    for sample_num in range(URM_train.nnz):\n",
    "\n",
    "        # Randomly pick sample\n",
    "        sample_index = rand() % n_interactions\n",
    "\n",
    "        user_id = URM_train_coo_row[sample_index]\n",
    "        item_id = URM_train_coo_col[sample_index]\n",
    "        rating = URM_train_coo_data[sample_index]\n",
    "\n",
    "        # Compute prediction\n",
    "        predicted_rating = 0.0\n",
    "        \n",
    "        for factor_index in range(num_factors):\n",
    "            predicted_rating += user_factors[user_id, factor_index] * item_factors[item_id, factor_index]\n",
    " \n",
    "        # Compute prediction error, or gradient\n",
    "        prediction_error = rating - predicted_rating\n",
    "        loss += prediction_error**2\n",
    "\n",
    "        # Copy original value to avoid messing up the updates\n",
    "        for factor_index in range(num_factors):\n",
    "            \n",
    "            H_i = item_factors[item_id,factor_index]\n",
    "            W_u = user_factors[user_id,factor_index]  \n",
    "\n",
    "            user_factors_update = prediction_error * H_i - regularization * W_u\n",
    "            item_factors_update = prediction_error * W_u - regularization * H_i\n",
    "\n",
    "            user_factors[user_id,factor_index] += learning_rate * user_factors_update \n",
    "            item_factors[item_id,factor_index] += learning_rate * item_factors_update    \n",
    "\n",
    "        # Print some stats\n",
    "        if (sample_num +1)% 500000 == 0:\n",
    "            elapsed_time = time.time() - start_time\n",
    "            samples_per_second = sample_num/elapsed_time\n",
    "            print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/sample_num, samples_per_second))\n",
    "\n",
    "    return loss, samples_per_second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 500000 in 0.58 seconds, loss is 1.92. Samples per second 862352.01\n",
      "Iteration 1000000 in 0.67 seconds, loss is 1.65. Samples per second 1501920.70\n",
      "Iteration 1500000 in 0.75 seconds, loss is 1.50. Samples per second 1989868.19\n",
      "Iteration 2000000 in 0.84 seconds, loss is 1.40. Samples per second 2375793.52\n",
      "Iteration 2500000 in 0.93 seconds, loss is 1.32. Samples per second 2691561.53\n",
      "Iteration 3000000 in 1.02 seconds, loss is 1.26. Samples per second 2953239.25\n",
      "Iteration 3500000 in 1.10 seconds, loss is 1.22. Samples per second 3167883.28\n",
      "Iteration 4000000 in 1.19 seconds, loss is 1.18. Samples per second 3353331.10\n",
      "Iteration 4500000 in 1.28 seconds, loss is 1.14. Samples per second 3513294.63\n",
      "Iteration 5000000 in 1.37 seconds, loss is 1.12. Samples per second 3658035.84\n",
      "Iteration 5500000 in 1.45 seconds, loss is 1.09. Samples per second 3780435.58\n",
      "Iteration 6000000 in 1.55 seconds, loss is 1.07. Samples per second 3881324.90\n",
      "Iteration 6500000 in 1.63 seconds, loss is 1.05. Samples per second 3978287.25\n",
      "Iteration 7000000 in 1.72 seconds, loss is 1.03. Samples per second 4062978.08\n",
      "Iteration 7500000 in 1.81 seconds, loss is 1.01. Samples per second 4141634.55\n",
      "Iteration 8000000 in 1.90 seconds, loss is 1.00. Samples per second 4215220.45\n"
     ]
    }
   ],
   "source": [
    "loss, samples_per_second = do_some_training(URM_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Estimated time with the previous training speed is 18.98 seconds, or 0.32 minutes\n"
     ]
    }
   ],
   "source": [
    "estimated_seconds = 8e6 * 10 / samples_per_second\n",
    "print(\"Estimated time with the previous training speed is {:.2f} seconds, or {:.2f} minutes\".format(estimated_seconds, estimated_seconds/60))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Works nicely, let's put an additional for loop to do multiple epochs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "from libc.stdlib cimport rand, srand, RAND_MAX\n",
    "\n",
    "def train_multiple_epochs(URM_train, learning_rate_input, n_epochs):\n",
    "    \n",
    "    URM_train_coo = URM_train.tocoo()\n",
    "    n_users, n_items = URM_train_coo.shape\n",
    "    cdef int n_interactions = URM_train.nnz\n",
    "    \n",
    "    cdef int sample_num, sample_index, user_id, item_id, factor_index\n",
    "    cdef double rating, predicted_rating, prediction_error\n",
    "\n",
    "    cdef int num_factors = 10\n",
    "    cdef double learning_rate = 1e-4\n",
    "    cdef double regularization = 1e-5\n",
    "    \n",
    "    cdef int[:] URM_train_coo_row = URM_train_coo.row\n",
    "    cdef int[:] URM_train_coo_col = URM_train_coo.col\n",
    "    cdef double[:] URM_train_coo_data = URM_train_coo.data\n",
    "\n",
    "    cdef double[:,:] user_factors = np.random.random((n_users, num_factors))\n",
    "    cdef double[:,:] item_factors = np.random.random((n_items, num_factors))\n",
    "    cdef double H_i, W_u\n",
    "    cdef double item_factors_update, user_factors_update\n",
    "                \n",
    "    cdef double loss = 0.0\n",
    "    cdef long start_time = time.time()\n",
    "    \n",
    "    for n_epoch in range(n_epochs):\n",
    "\n",
    "        loss = 0.0\n",
    "        start_time = time.time()\n",
    "\n",
    "        for sample_num in range(URM_train.nnz):\n",
    "\n",
    "            # Randomly pick sample\n",
    "            sample_index = rand() % n_interactions\n",
    "\n",
    "            user_id = URM_train_coo_row[sample_index]\n",
    "            item_id = URM_train_coo_col[sample_index]\n",
    "            rating = URM_train_coo_data[sample_index]\n",
    "\n",
    "            # Compute prediction\n",
    "            predicted_rating = 0.0\n",
    "\n",
    "            for factor_index in range(num_factors):\n",
    "                predicted_rating += user_factors[user_id, factor_index] * item_factors[item_id, factor_index]\n",
    "\n",
    "            # Compute prediction error, or gradient\n",
    "            prediction_error = rating - predicted_rating\n",
    "            loss += prediction_error**2\n",
    "\n",
    "            # Copy original value to avoid messing up the updates\n",
    "            for factor_index in range(num_factors):\n",
    "\n",
    "                H_i = item_factors[item_id,factor_index]\n",
    "                W_u = user_factors[user_id,factor_index]  \n",
    "\n",
    "                user_factors_update = prediction_error * H_i - regularization * W_u\n",
    "                item_factors_update = prediction_error * W_u - regularization * H_i\n",
    "\n",
    "                user_factors[user_id,factor_index] += learning_rate * user_factors_update \n",
    "                item_factors[item_id,factor_index] += learning_rate * item_factors_update    \n",
    "\n",
    "#             # Print some stats\n",
    "#             if (sample_num +1)% 1000000 == 0:\n",
    "#                 elapsed_time = time.time() - start_time\n",
    "#                 samples_per_second = sample_num/elapsed_time\n",
    "#                 print(\"Iteration {} in {:.2f} seconds, loss is {:.2f}. Samples per second {:.2f}\".format(sample_num+1, elapsed_time, loss/sample_num, samples_per_second))\n",
    "\n",
    "            \n",
    "        elapsed_time = time.time() - start_time\n",
    "        samples_per_second = sample_num/elapsed_time\n",
    "     \n",
    "        print(\"Epoch {} complete in in {:.2f} seconds, loss is {:.3E}. Samples per second {:.2f}\".format(n_epoch+1, time.time() - start_time, loss/sample_num, samples_per_second))\n",
    "\n",
    "    return np.array(user_factors), np.array(item_factors), loss, samples_per_second    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Epoch 1 complete in in 1.44 seconds, loss is 9.996E-01. Samples per second 5540332.54\n",
      "Epoch 2 complete in in 1.86 seconds, loss is 7.063E-01. Samples per second 4300998.79\n",
      "Epoch 3 complete in in 2.28 seconds, loss is 6.368E-01. Samples per second 3510142.54\n",
      "Epoch 4 complete in in 1.70 seconds, loss is 5.924E-01. Samples per second 4699807.44\n",
      "Epoch 5 complete in in 2.12 seconds, loss is 5.539E-01. Samples per second 3773097.43\n",
      "Epoch 6 complete in in 1.54 seconds, loss is 5.182E-01. Samples per second 5200338.93\n",
      "Epoch 7 complete in in 1.96 seconds, loss is 4.830E-01. Samples per second 4080720.42\n",
      "Epoch 8 complete in in 2.38 seconds, loss is 4.497E-01. Samples per second 3364858.22\n",
      "Epoch 9 complete in in 1.80 seconds, loss is 4.189E-01. Samples per second 4452850.38\n",
      "Epoch 10 complete in in 2.21 seconds, loss is 3.913E-01. Samples per second 3625358.64\n"
     ]
    }
   ],
   "source": [
    "n_items = URM_train.shape[1]\n",
    "learning_rate = 1e-3\n",
    "    \n",
    "user_factors, item_factors, loss, samples_per_second = \\\n",
    "    train_multiple_epochs(URM_train, learning_rate, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### From 20 minutes of training time to a few seconds..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
